#include "stdio.h"
#include "math.h"
int check(int a,int n);
main(){
	int n1,m,n,i,b,min;
	scanf("%d",&n1);
	while(n1--){
		scanf("%d%d",&n,&m);
		i=2;
		min=check(2,n);
		while(i<=(int)(sqrt(m)+0.000000001)){
			b=0;
			while(m%i==0){
				b++;
				m/=i;
			}
			if(b!=0){
				min=check(i,n)/b<min?check(i,n)/b:min;
			}
			i++;
		}
		if(m!=1)
			min=check(m,n)<min?check(m,n):min;
		printf("%d\n",min);
	}	
}
int check(int a,int n){
	int i,t,t1,s,n1,count=0;
	t=(int)(log(n)/log(a)+0.000000001);
	t1=(int)pow(a,t);
	s=(t1-1)/(a-1);
	if(t1==n)
		return s;
	else{
		count=n/t1*s;
		if(n%t1)
		count+=check(a,n%t1);
	}
	return count;
}